package com.xqx.mergeSort;

public class MergeSort {
    //合并两个数组
    public static void MemeryArrayTest(int[] a,int n,int[] b,int m,int[] c){
        int i,j,k;
        i=j=k=0;
        while (i<n&&j<m){
            if (a[i] < b[j])
                c[k++]=a[i++];
            else
                c[k++]=b[j++];
        }
        while (i<n)
            c[k++]=a[i++];
        while (j<m)
            c[k++]=b[j++];
    }
    public static void merge_sort(int[] a,int first,int last,int temp[]){
        if (first<last){
            int middle=(first+last)/2;
            merge_sort(a,first,middle,temp);  //左半部分排好序
            merge_sort(a,middle+1,last,temp);  //右半部分排好序
            mergeArray(a,first,middle,last,temp);  //合并左右部分
        }
    }
    //合并：将两个序列a[first-middle],a[middle+1-end]合并
    public static void mergeArray(int a[],int first,int middle,int end,int temp[]){
        int i=first;
        int m=middle;
        int j=middle+1;
        int n=end;
        int k=0;
        while (i<=m && j<=n){
            if (a[i]<=a[j]){
                temp[k]=a[i];
                k++;
                i++;
            }else {
                temp[k]=a[j];
                k++;
                j++;
            }
        }
        while (i<=m){
            temp[k]=a[i];
            k++;
            i++;
        }
        while (j<=n){
            temp[k]=a[j];
            k++;
            j++;
        }
        for (int ii = 0; ii < k ; ii++) {
            a[first+ii]=temp[ii];
        }
    }
}
